package arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

public class ArrayArithmetic {
    //    On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
    //    Once you pay the cost, you can either climb one or two steps. You need to find minimum cost
    // to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.746
    public int minCostClimbingStairs(int[] cost) {
        int sum = 0;
        int step_1 = 0;
        int step_2 = 0;
        for (int i = 2; i <= cost.length; i++) {
            sum = step_1 + cost[i - 2] < step_2 + cost[i - 1] ? step_1 + cost[i - 2] : step_2 + cost[i - 1];
            step_1 = step_2;
            step_2 = sum;
        }
        return sum;
    }

    //    Given an array of integers nums, write a method that returns the "pivot" index of this array.
    //    We define the pivot index as the index where the sum of the numbers to the left of the index
    // is equal to the sum of the numbers to the right of the index.
    //    If no such index exists, we should return -1. If there are multiple pivot indexes,
    // you should return the left-most pivot index. 724
    public int pivotIndex(int[] nums) {

        if (nums.length == 0) {
            return -1;
        }
        int leftSum;
        int rightSum;
        int mid;
        for (mid = 0; mid < nums.length; mid++) {
            leftSum = rightSum = 0;
            for (int i = 0; i < mid; i++) {
                leftSum += nums[i];
            }
            for (int i = mid + 1; i < nums.length; i++) {
                rightSum += nums[i];
            }
            if (leftSum == rightSum) {
                return mid;
            }
        }
        return -1;
    }

    //    Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.2个数组同时出现的字符串值
    public int findLength(int[] A, int[] B) {
        int[][] c = new int[A.length + 1][B.length + 1];
        int lenth = 0;
        ArrayList<Integer> minlist = new ArrayList<>();
        for (int i = 1; i < A.length + 1; i++) {
            for (int j = 1; j < B.length + 1; j++) {
                if (A[i - 1] == B[j - 1]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                }
                if (lenth < c[i][j])
                    lenth = c[i][j];
            }
        }
        return lenth;
    }

    //埃拉托色尼筛选法
    public ArrayList<Integer> sieve(int n) {

        int[] sieve = new int[n + 1];
        for (int i = 2; i < sieve.length; i++)
            sieve[i] = i;
        for (int i = 2; i < n; i++) {
            if (sieve[i] == 0)
                continue;
            for (int j = i + 1; j < n; j++) {
                if (sieve[j] == 0)
                    continue;
                if (sieve[j] % sieve[i] == 0)
                    sieve[j] = 0;
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (Integer num : sieve) {
            if (num != 0)
                result.add(num);
        }
        return result;
    }

    //一年中的第几天
    public int numerOfday(int year, int month, int day) {
        if (year <= 0 || month <= 0 || day <= 0 || month > 12)
            return 0;
        int num = 0;
        switch (month - 1) {
            case 11:
                num += 30;
            case 10:
                num += 31;
            case 9:
                num += 30;
            case 8:
                num += 31;
            case 7:
                num += 31;
            case 6:
                num += 30;
            case 5:
                num += 31;
            case 4:
                num += 30;
            case 3:
                num += 31;
            case 2:
                num += 28;
            case 1:
                num += 31;
        }
        int checkYear = year % 400;
        if (checkYear == 0) {
            num++;
        } else {
            checkYear = year % 4;
            if (checkYear == 0) {
                num++;
            }
        }

        return num + day;
    }

    //leetcode 42 接雨水
    public int trap(int[] height) {
        int water = 0;
        int[] check = new int[height.length];
        if (height.length < 3)
            return 0;
        boolean isAdd = false;
        for (int i = 0; i < height.length - 1; i++) {
            if (height[i] == 0)
                continue;
            int start = height[i];
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] < start) {
                    isAdd = true;
                }
                if (height[j] >= start) {
                    if (isAdd) {
                        //计算水量
                        for (int k = i + 1; k < j; k++) {
                            check[k] = start - height[k];
                            water += start - height[k];
                        }
                        i = j - 1;
                        isAdd = false;
                        break;
                    } else break;
                }

            }
        }
        isAdd = false;
        for (int i = height.length - 1; i > 0; i--) {
            if (height[i] == 0)
                continue;
            isAdd = false;
            int start = height[i];
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] < start) {
                    isAdd = true;
                }
                if (height[j] == start) {
                    i = j + 1;
                    isAdd = false;
                    break;
                }

                if (height[j] > start) {
                    if (isAdd) {
                        //计算水量
                        for (int k = j + 1; k < i; k++) {
                            if (check[k] == 0 || start - height[k] > check[k])
                                water = water - check[k] + start - height[k];
                        }
                        i = j + 1;
                        isAdd = false;
                        break;
                    } else break;
                }
            }
        }
        return water;
    }

    //    70. 爬楼梯
    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        int[] high = new int[n + 1];
        high[1] = 1;
        high[2] = 2;
        for (int i = 3; i < high.length; i++) {
            high[i] = high[i - 2] + high[i - 1];
        }
        return high[high.length - 1];
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (j - i > k)
                    break;
                if (Math.abs((long) nums[i] - nums[j]) <= t && j - i <= k)
                    return true;
            }
        }
        return false;
    }

    //    11. 盛最多水的容器
    public int maxArea(int[] height) {
        if (height.length < 2) {
            return 0;
        }
        int max = 0;
        int i = 0, k = height.length - 1;
        while (i < k) {
            int area = height[i] > height[k] ? height[k] * (k-- - i) : height[i] * (k - i++);
            max = max > area ? max : area;
        }
        return max;
    }

    //118.杨辉三角
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0)
            return new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        l.add(1);
        list.add(l);
        for (int i = 1; i < numRows; i++) {
            List<Integer> l1 = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0)
                    l1.add(list.get(i - 1).get(j));
                else if (j == i)
                    l1.add(list.get(i - 1).get(j - 1));
                else
                    l1.add(list.get(i - 1).get(j) + list.get(i - 1).get(j - 1));
            }
            list.add(l1);
        }
        return list;
    }

    //643. 子数组最大平均数 I (数组滑动，减少重复垒加)
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int j = 0; j < k; j++) {
            sum += nums[j];
        }
        if (max < sum) {
            max = sum;
        }
        for (int i = 0; i < nums.length - k; i++) {
            sum = sum - nums[i] + nums[i + k];
            if (max < sum) {
                max = sum;
            }
        }
        return max / (double) k;
    }

    // 455. 分发饼干
    public int findContentChildren(int[] g, int[] s) {
        if (g.length == 0 || s.length == 0)
            return 0;
        int result = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int k = 0;
        for (int i = 0; i < g.length; i++) {
            for (int j = k; j < s.length; j++) {
                if (g[i] <= s[j]) {
                    result++;
                    k = j + 1;
                    break;
                }
            }
        }
        return result;
    }

    //    134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int start = 0;
        int temp = 0;
        for (int i = 0; i < gas.length; i++) {
            temp += gas[i] - cost[i];
            if (temp < 0) {
                sum += temp;
                start = i + 1;
                temp = 0;
            }
        }
        sum += temp;
        return sum >= 0 ? start : -1;
    }

    //41. 缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        if (nums.length == 0)
            return 1;
        if (nums.length == 1)
            return nums[0] != 1 ? 1 : 2;
        Arrays.sort(nums);
        int index = 0;
        int num = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                index = i;
                break;
            }
        }
        for (int i = index; i < nums.length; i++) {
            if (nums[i] < num)
                continue;
            if (nums[i] - num > 0)
                return num;
            num++;
        }
        return num;

    }

    public boolean validMountainArray(int[] A) {
        int length = A.length;
        int index = 1;
        while (index < length && A[index - 1] < A[index]) index++;
        if (index == length || index == 0) return false;
        while (index < length && A[index - 1] > A[index]) index++;
        if (index == length)
             return true;
        return false;
    }
}
